package com.liuyfly.leetcode.questions;

import lombok.extern.slf4j.Slf4j;

/**
 * @author liuyangfang at 2022-10-20 19:57
 */
@Slf4j
public class Question0779 {
    public static int kthGrammar(int n, int k) {
        int temp = (int) Math.pow(2, n - 2);
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            if (k == 1) {
                return 0;
            } else {
                return 1;
            }
        }
        if (k <= (1 << (n - 2))) {
            return kthGrammar(n - 1, k);
        } else {
            return 1 ^ kthGrammar(n - 1, k - temp);
        }
    }

    public static void main(String[] args) {
        int n = 5, k = 4;
        for (int k2 = 1; k2 <= (1 << (n - 1)); k2++) {
            int result = kthGrammar(n, k2);
            log.info("result:{}", result);
        }
    }

}
